Data may be stored locally or remotely according to a variety of storage configurations and implementations. For instance, cloud computing is a recent development related to the deployment of remote servers and software networks that provide for centralized data storage and online access to resources and services, referred to as “cloud services.” A set of cloud servers may host resources/services for a single user (a “tenant”), or for multiple related or unrelated users (a “multi-tenant” system). Similarly, data may be stored “on-site” by an entity, and may be accessed by that entity in that on-site data storage.
Data breaches are arguably the main deterrent for the adoption of cloud services for applications that manage sensitive, business critical information. On a public cloud, applications must guard against potentially malicious cloud administrators, malicious co-tenants, and other entities that can obtain access to data through various legal means. Since the compute and storage platform itself cannot be trusted, any data that appears in cleartext (data that is not encrypted) anywhere on the cloud platform (on disk, in memory, over the wire, etc.) has to be considered susceptible to leakage or malicious corruption. In vertical industries such as finance, banking, and healthcare, compliance requirements mandate strong protection against these types of threats.
Accordingly, in some cases, a database server may store encrypted data, but have no access to the encryption keys for security reasons. This guarantees that any data stored in the database is encrypted until it passes to the client application (e.g., an intermediate application managed by the client entity), which runs in a protected environment. For example, the database server may use partially homomorphic encryption (PHE) schemes, secure hardware, and/or other secure forms of computation to process data in encrypted form, because the database server does not have access to the encryption keys. PHE schemes permit a restricted class of operations, but not all operations, to be performed directly on encrypted data without requiring encryption keys. Due to these security requirements and encrypted data computing constraints, handling queries on databases in a secure and efficient manner is difficult to implement.